package Aleehot100;

import java.util.ArrayList;
import java.util.List;

/**
 * ClassName: c059
 * Package: Aleehot100
 * Description:22. 括号生成
 *
 * @Author BCXJ
 * @Create 2025/8/10 12:36
 * @Version 1.0
 * @Since 1.0
 */
public class c059 {
    public static void main(String[] args) {
        System.out.println(generateParenthesis(3));
    }

    static List<String> res = new ArrayList<>();
    public static List<String> generateParenthesis(int n) {
        res.clear();
        process(0, 0, n, new StringBuilder());
        return res;
    }

    /**
     *
     * @param open ( 的个数
     * @param close } 的个数
     * @param max 最大的括号对个数
     * @param str 目前的str
     */
    private static void process(int open, int close, int max, StringBuilder str) {
        if(open + close == 2 * max) {
            res.add(str.toString());
            return;
        }

        if(open < max) {
            str.append('(');
            process(open + 1, close, max, str);
            str.deleteCharAt(str.length() - 1); // 删除之前加入的 括号，方便回溯
        }
        if(close < open) {
            str.append(')');
            process(open, close + 1, max, str);
            str.deleteCharAt(str.length() - 1); // 下标从0开始
        }
    }
}
